// Copyright 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "content/browser/find_request_manager.h"

#include "content/browser/frame_host/render_frame_host_impl.h"
#include "content/browser/web_contents/web_contents_impl.h"
#include "content/common/frame_messages.h"
#include "content/common/input_messages.h"

namespace content {

namespace {

    // Returns the deepest last child frame under |node|/|rfh| in the frame tree.
    FrameTreeNode* GetDeepestLastChild(FrameTreeNode* node)
    {
        while (node->child_count())
            node = node->child_at(node->child_count() - 1);
        return node;
    }
    RenderFrameHost* GetDeepestLastChild(RenderFrameHost* rfh)
    {
        FrameTreeNode* node = static_cast<RenderFrameHostImpl*>(rfh)->frame_tree_node();
        return GetDeepestLastChild(node)->current_frame_host();
    }

    // Returns the FrameTreeNode directly after |node| in the frame tree in search
    // order, or nullptr if one does not exist. If |wrap| is set, then wrapping
    // between the first and last frames is permitted. Note that this traversal
    // follows the same ordering as in blink::FrameTree::traverseNextWithWrap().
    FrameTreeNode* TraverseNext(FrameTreeNode* node, bool wrap)
    {
        if (node->child_count())
            return node->child_at(0);

        FrameTreeNode* sibling = node->NextSibling();
        while (!sibling) {
            if (!node->parent())
                return wrap ? node : nullptr;
            node = node->parent();
            sibling = node->NextSibling();
        }
        return sibling;
    }

    // Returns the FrameTreeNode directly before |node| in the frame tree in search
    // order, or nullptr if one does not exist. If |wrap| is set, then wrapping
    // between the first and last frames is permitted. Note that this traversal
    // follows the same ordering as in blink::FrameTree::traversePreviousWithWrap().
    FrameTreeNode* TraversePrevious(FrameTreeNode* node, bool wrap)
    {
        if (FrameTreeNode* previous_sibling = node->PreviousSibling())
            return GetDeepestLastChild(previous_sibling);
        if (node->parent())
            return node->parent();
        return wrap ? GetDeepestLastChild(node) : nullptr;
    }

    // The same as either TraverseNext() or TraversePrevious() depending on
    // |forward|.
    FrameTreeNode* TraverseNode(FrameTreeNode* node, bool forward, bool wrap)
    {
        return forward ? TraverseNext(node, wrap) : TraversePrevious(node, wrap);
    }

} // namespace

#if defined(OS_ANDROID)
FindRequestManager::ActivateNearestFindResultState::
    ActivateNearestFindResultState()
    = default;
FindRequestManager::ActivateNearestFindResultState::
    ActivateNearestFindResultState(float x, float y)
    : current_request_id(GetNextID())
    , x(x)
    , y(y)
{
}
FindRequestManager::ActivateNearestFindResultState::
    ~ActivateNearestFindResultState() { }

FindRequestManager::FrameRects::FrameRects() = default;
FindRequestManager::FrameRects::FrameRects(const std::vector<gfx::RectF>& rects,
    int version)
    : rects(rects)
    , version(version)
{
}
FindRequestManager::FrameRects::~FrameRects() { }

FindRequestManager::FindMatchRectsState::FindMatchRectsState() = default;
FindRequestManager::FindMatchRectsState::~FindMatchRectsState() { }
#endif

// static
const int FindRequestManager::kInvalidId = -1;

FindRequestManager::FindRequestManager(WebContentsImpl* web_contents)
    : WebContentsObserver(web_contents)
    , contents_(web_contents)
    , current_session_id_(kInvalidId)
    , pending_find_next_reply_(nullptr)
    , pending_active_match_ordinal_(false)
    , number_of_matches_(0)
    , active_frame_(nullptr)
    , relative_active_match_ordinal_(0)
    , active_match_ordinal_(0)
    , last_reported_id_(kInvalidId)
{
}

FindRequestManager::~FindRequestManager() { }

void FindRequestManager::Find(int request_id,
    const base::string16& search_text,
    const blink::WebFindOptions& options)
{
    // Every find request must have a unique ID, and these IDs must strictly
    // increase so that newer requests always have greater IDs than older
    // requests.
    DCHECK_GT(request_id, current_request_.id);
    DCHECK_GT(request_id, current_session_id_);

    // If this is a new find session, clear any queued requests from last session.
    if (!options.findNext)
        find_request_queue_ = std::queue<FindRequest>();

    find_request_queue_.emplace(request_id, search_text, options);
    if (find_request_queue_.size() == 1)
        FindInternal(find_request_queue_.front());
}

void FindRequestManager::StopFinding(StopFindAction action)
{
    contents_->SendToAllFrames(
        new FrameMsg_StopFinding(MSG_ROUTING_NONE, action));

    current_session_id_ = kInvalidId;
#if defined(OS_ANDROID)
    // It is important that these pending replies are cleared whenever a find
    // session ends, so that subsequent replies for the old session are ignored.
    activate_.pending_replies.clear();
    match_rects_.pending_replies.clear();
#endif
}

void FindRequestManager::OnFindReply(RenderFrameHost* rfh,
    int request_id,
    int number_of_matches,
    const gfx::Rect& selection_rect,
    int active_match_ordinal,
    bool final_update)
{
    // Ignore stale replies from abandoned find sessions.
    if (current_session_id_ == kInvalidId || request_id < current_session_id_)
        return;
    DCHECK(CheckFrame(rfh));

    // Update the stored find results.

    DCHECK_GE(number_of_matches, -1);
    DCHECK_GE(active_match_ordinal, -1);

    // Check for an update to the number of matches.
    if (number_of_matches != -1) {
        DCHECK_GE(number_of_matches, 0);
        auto matches_per_frame_it = matches_per_frame_.find(rfh);
        if (int matches_delta = number_of_matches - matches_per_frame_it->second) {
            // Increment the global number of matches by the number of additional
            // matches found for this frame.
            number_of_matches_ += matches_delta;
            matches_per_frame_it->second = number_of_matches;

            // The active match ordinal may need updating since the number of matches
            // before the active match may have changed.
            if (rfh != active_frame_)
                UpdateActiveMatchOrdinal();
        }
    }

    // Check for an update to the selection rect.
    if (!selection_rect.IsEmpty())
        selection_rect_ = selection_rect;

    // Check for an update to the active match ordinal.
    if (active_match_ordinal > 0) {
        if (rfh == active_frame_) {
            active_match_ordinal_ += active_match_ordinal - relative_active_match_ordinal_;
            relative_active_match_ordinal_ = active_match_ordinal;
        } else {
            if (active_frame_) {
                // The new active match is in a different frame than the previous, so
                // the previous active frame needs to be informed (to clear its active
                // match highlighting).
                active_frame_->Send(new FrameMsg_ClearActiveFindMatch(
                    active_frame_->GetRoutingID()));
            }
            active_frame_ = rfh;
            relative_active_match_ordinal_ = active_match_ordinal;
            UpdateActiveMatchOrdinal();
        }
        if (pending_active_match_ordinal_ && request_id == current_request_.id)
            pending_active_match_ordinal_ = false;
        AdvanceQueue(request_id);
    }

    if (!final_update) {
        NotifyFindReply(request_id, false /* final_update */);
        return;
    }

    // This is the final update for this frame for the current find operation.

    pending_initial_replies_.erase(rfh);
    if (request_id == current_session_id_ && !pending_initial_replies_.empty()) {
        NotifyFindReply(request_id, false /* final_update */);
        return;
    }

    // This is the final update for the current find operation.

    if (request_id == current_request_.id && request_id != current_session_id_) {
        DCHECK(current_request_.options.findNext);
        DCHECK_EQ(pending_find_next_reply_, rfh);
        pending_find_next_reply_ = nullptr;
    }

    FinalUpdateReceived(request_id, rfh);
}

void FindRequestManager::RemoveFrame(RenderFrameHost* rfh)
{
    if (current_session_id_ == kInvalidId || !CheckFrame(rfh))
        return;

    // If matches are counted for the frame that is being removed, decrement the
    // match total before erasing that entry.
    auto it = matches_per_frame_.find(rfh);
    if (it != matches_per_frame_.end()) {
        number_of_matches_ -= it->second;
        matches_per_frame_.erase(it);
    }

    // Update the active match ordinal, since it may have changed.
    if (active_frame_ == rfh) {
        active_frame_ = nullptr;
        relative_active_match_ordinal_ = 0;
        selection_rect_ = gfx::Rect();
    }
    UpdateActiveMatchOrdinal();

#if defined(OS_ANDROID)
    // The removed frame may contain the nearest find result known so far. Note
    // that once all queried frames have responded, if this result was the overall
    // nearest, then no activation will occur.
    if (rfh == activate_.nearest_frame)
        activate_.nearest_frame = nullptr;

    // Match rects in the removed frame are no longer relevant.
    if (match_rects_.frame_rects.count(rfh)) {
        match_rects_.frame_rects.erase(rfh);
        ++match_rects_.known_version;
    }

    // A reply should not be expected from the removed frame.
    RemoveNearestFindResultPendingReply(rfh);
    RemoveFindMatchRectsPendingReply(rfh);
#endif

    // If no pending find replies are expected for the removed frame, then just
    // report the updated results.
    if (!pending_initial_replies_.count(rfh) && pending_find_next_reply_ != rfh) {
        bool final_update = pending_initial_replies_.empty() && !pending_find_next_reply_;
        NotifyFindReply(current_session_id_, final_update);
        return;
    }

    if (pending_initial_replies_.count(rfh)) {
        // A reply should not be expected from the removed frame.
        pending_initial_replies_.erase(rfh);
        if (pending_initial_replies_.empty()) {
            FinalUpdateReceived(current_session_id_, rfh);
        }
    }

    if (pending_find_next_reply_ == rfh) {
        // A reply should not be expected from the removed frame.
        pending_find_next_reply_ = nullptr;
        FinalUpdateReceived(current_request_.id, rfh);
    }
}

#if defined(OS_ANDROID)
void FindRequestManager::ActivateNearestFindResult(float x, float y)
{
    if (current_session_id_ == kInvalidId)
        return;

    activate_ = ActivateNearestFindResultState(x, y);

    // Request from each frame the distance to the nearest find result (in that
    // frame) from the point (x, y), defined in find-in-page coordinates.
    for (FrameTreeNode* node : contents_->GetFrameTree()->Nodes()) {
        RenderFrameHost* rfh = node->current_frame_host();

        if (!CheckFrame(rfh) || !rfh->IsRenderFrameLive())
            continue;

        activate_.pending_replies.insert(rfh);
        rfh->Send(new FrameMsg_GetNearestFindResult(
            rfh->GetRoutingID(), activate_.current_request_id,
            activate_.x, activate_.y));
    }
}

void FindRequestManager::OnGetNearestFindResultReply(RenderFrameHost* rfh,
    int request_id,
    float distance)
{
    if (request_id != activate_.current_request_id || !activate_.pending_replies.count(rfh)) {
        return;
    }

    // Check if this frame has a nearer find result than the current nearest.
    if (distance < activate_.nearest_distance) {
        activate_.nearest_frame = rfh;
        activate_.nearest_distance = distance;
    }

    RemoveNearestFindResultPendingReply(rfh);
}

void FindRequestManager::RequestFindMatchRects(int current_version)
{
    match_rects_.pending_replies.clear();
    match_rects_.request_version = current_version;

    // Request the latest find match rects from each frame.
    for (FrameTreeNode* node : contents_->GetFrameTree()->Nodes()) {
        RenderFrameHost* rfh = node->current_frame_host();

        if (!CheckFrame(rfh) || !rfh->IsRenderFrameLive())
            continue;

        match_rects_.pending_replies.insert(rfh);
        auto it = match_rects_.frame_rects.find(rfh);
        int version = (it != match_rects_.frame_rects.end())
            ? it->second.version
            : kInvalidId;
        rfh->Send(new FrameMsg_FindMatchRects(rfh->GetRoutingID(), version));
    }
}

void FindRequestManager::OnFindMatchRectsReply(
    RenderFrameHost* rfh,
    int version,
    const std::vector<gfx::RectF>& rects,
    const gfx::RectF& active_rect)
{
    auto it = match_rects_.frame_rects.find(rfh);
    if (it == match_rects_.frame_rects.end() || it->second.version != version) {
        // New version of rects has been received, so update the data.
        match_rects_.frame_rects[rfh] = FrameRects(rects, version);
        ++match_rects_.known_version;
    }
    if (!active_rect.IsEmpty())
        match_rects_.active_rect = active_rect;
    RemoveFindMatchRectsPendingReply(rfh);
}
#endif

void FindRequestManager::DidFinishLoad(RenderFrameHost* rfh,
    const GURL& validated_url)
{
    if (current_session_id_ == kInvalidId)
        return;

    RemoveFrame(rfh);
    AddFrame(rfh, true /* force */);
}

void FindRequestManager::RenderFrameDeleted(RenderFrameHost* rfh)
{
    RemoveFrame(rfh);
}

void FindRequestManager::RenderFrameHostChanged(RenderFrameHost* old_host,
    RenderFrameHost* new_host)
{
    RemoveFrame(old_host);
}

void FindRequestManager::FrameDeleted(RenderFrameHost* rfh)
{
    RemoveFrame(rfh);
}

void FindRequestManager::Reset(const FindRequest& initial_request)
{
    current_session_id_ = initial_request.id;
    current_request_ = initial_request;
    pending_initial_replies_.clear();
    pending_find_next_reply_ = nullptr;
    pending_active_match_ordinal_ = true;
    matches_per_frame_.clear();
    number_of_matches_ = 0;
    active_frame_ = nullptr;
    relative_active_match_ordinal_ = 0;
    active_match_ordinal_ = 0;
    selection_rect_ = gfx::Rect();
    last_reported_id_ = kInvalidId;
#if defined(OS_ANDROID)
    activate_ = ActivateNearestFindResultState();
    match_rects_.pending_replies.clear();
#endif
}

void FindRequestManager::FindInternal(const FindRequest& request)
{
    DCHECK_GT(request.id, current_request_.id);
    DCHECK_GT(request.id, current_session_id_);

    if (request.options.findNext) {
        // This is a find next operation.

        // This implies that there is an ongoing find session with the same search
        // text.
        DCHECK_GE(current_session_id_, 0);
        DCHECK_EQ(request.search_text, current_request_.search_text);

        // The find next request will be directed at the focused frame if there is
        // one, or the first frame with matches otherwise.
        RenderFrameHost* target_rfh = contents_->GetFocusedFrame();
        if (!target_rfh || !CheckFrame(target_rfh))
            target_rfh = GetInitialFrame(request.options.forward);

        SendFindIPC(request, target_rfh);
        current_request_ = request;
        pending_active_match_ordinal_ = true;
        return;
    }

    // This is an initial find operation.
    Reset(request);
    for (FrameTreeNode* node : contents_->GetFrameTree()->Nodes())
        AddFrame(node->current_frame_host(), false /* force */);
}

void FindRequestManager::AdvanceQueue(int request_id)
{
    if (find_request_queue_.empty() || request_id != find_request_queue_.front().id) {
        return;
    }

    find_request_queue_.pop();
    if (!find_request_queue_.empty())
        FindInternal(find_request_queue_.front());
}

void FindRequestManager::SendFindIPC(const FindRequest& request,
    RenderFrameHost* rfh)
{
    DCHECK(CheckFrame(rfh));
    DCHECK(rfh->IsRenderFrameLive());

    if (request.options.findNext)
        pending_find_next_reply_ = rfh;
    else
        pending_initial_replies_.insert(rfh);

    rfh->Send(new FrameMsg_Find(rfh->GetRoutingID(), request.id,
        request.search_text, request.options));
}

void FindRequestManager::NotifyFindReply(int request_id, bool final_update)
{
    if (request_id == kInvalidId) {
        NOTREACHED();
        return;
    }

    // Ensure that replies are not reported with IDs lower than the ID of the
    // latest request we have results from.
    if (request_id < last_reported_id_)
        request_id = last_reported_id_;
    else
        last_reported_id_ = request_id;

    contents_->NotifyFindReply(request_id, number_of_matches_, selection_rect_,
        active_match_ordinal_, final_update);
}

RenderFrameHost* FindRequestManager::GetInitialFrame(bool forward) const
{
    RenderFrameHost* rfh = contents_->GetMainFrame();

    if (!forward)
        rfh = GetDeepestLastChild(rfh);

    return rfh;
}

RenderFrameHost* FindRequestManager::Traverse(RenderFrameHost* from_rfh,
    bool forward,
    bool matches_only,
    bool wrap) const
{
    FrameTreeNode* node = static_cast<RenderFrameHostImpl*>(from_rfh)->frame_tree_node();

    while ((node = TraverseNode(node, forward, wrap)) != nullptr) {
        if (!CheckFrame(node->current_frame_host()))
            continue;
        RenderFrameHost* current_rfh = node->current_frame_host();
        if (!matches_only || matches_per_frame_.find(current_rfh)->second || pending_initial_replies_.count(current_rfh)) {
            // Note that if there is still a pending reply expected for this frame,
            // then it may have unaccounted matches and will not be skipped via
            // |matches_only|.
            return node->current_frame_host();
        }
        if (wrap && node->current_frame_host() == from_rfh)
            return nullptr;
    }

    return nullptr;
}

void FindRequestManager::AddFrame(RenderFrameHost* rfh, bool force)
{
    if (!rfh || !rfh->IsRenderFrameLive())
        return;

    // A frame that is already being searched should not normally be added again.
    DCHECK(force || !CheckFrame(rfh));

    matches_per_frame_[rfh] = 0;

    FindRequest request = current_request_;
    request.id = current_session_id_;
    request.options.findNext = false;
    request.options.force = force;
    SendFindIPC(request, rfh);
}

bool FindRequestManager::CheckFrame(RenderFrameHost* rfh) const
{
    return rfh && matches_per_frame_.count(rfh);
}

void FindRequestManager::UpdateActiveMatchOrdinal()
{
    active_match_ordinal_ = 0;

    if (!active_frame_ || !relative_active_match_ordinal_) {
        DCHECK(!active_frame_ && !relative_active_match_ordinal_);
        return;
    }

    // Traverse the frame tree backwards (in search order) and count all of the
    // matches in frames before the frame with the active match, in order to
    // determine the overall active match ordinal.
    RenderFrameHost* frame = active_frame_;
    while ((frame = Traverse(frame,
                false /* forward */,
                true /* matches_only */,
                false /* wrap */))
        != nullptr) {
        active_match_ordinal_ += matches_per_frame_[frame];
    }
    active_match_ordinal_ += relative_active_match_ordinal_;
}

void FindRequestManager::FinalUpdateReceived(int request_id,
    RenderFrameHost* rfh)
{
    if (!number_of_matches_ || (active_match_ordinal_ && !pending_active_match_ordinal_) || pending_find_next_reply_) {
        // All the find results for |request_id| are in and ready to report. Note
        // that |final_update| will be set to false if there are still pending
        // replies expected from the initial find request.
        NotifyFindReply(request_id,
            pending_initial_replies_.empty() /* final_update */);
        AdvanceQueue(request_id);
        return;
    }

    // There are matches, but no active match was returned, so another find next
    // request must be sent.

    RenderFrameHost* target_rfh;
    if (request_id == current_request_.id && current_request_.options.findNext) {
        // If this was a find next operation, then the active match will be in the
        // next frame with matches after this one.
        target_rfh = Traverse(rfh,
            current_request_.options.forward,
            true /* matches_only */,
            true /* wrap */);
    } else if ((target_rfh = contents_->GetFocusedFrame()) != nullptr) {
        // Otherwise, if there is a focused frame, then the active match will be in
        // the next frame with matches after that one.
        target_rfh = Traverse(target_rfh,
            current_request_.options.forward,
            true /* matches_only */,
            true /* wrap */);
    } else {
        // Otherwise, the first frame with matches will have the active match.
        target_rfh = GetInitialFrame(current_request_.options.forward);
        if (!CheckFrame(target_rfh) || !matches_per_frame_[target_rfh]) {
            target_rfh = Traverse(target_rfh,
                current_request_.options.forward,
                true /* matches_only */,
                false /* wrap */);
        }
    }
    DCHECK(target_rfh);

    // Forward the find reply without |final_update| set because the active match
    // has not yet been found.
    NotifyFindReply(request_id, false /* final_update */);

    current_request_.options.findNext = true;
    SendFindIPC(current_request_, target_rfh);
}

#if defined(OS_ANDROID)
void FindRequestManager::RemoveNearestFindResultPendingReply(
    RenderFrameHost* rfh)
{
    auto it = activate_.pending_replies.find(rfh);
    if (it == activate_.pending_replies.end())
        return;

    activate_.pending_replies.erase(it);
    if (activate_.pending_replies.empty() && CheckFrame(activate_.nearest_frame)) {
        activate_.nearest_frame->Send(new FrameMsg_ActivateNearestFindResult(
            activate_.nearest_frame->GetRoutingID(),
            current_session_id_, activate_.x, activate_.y));
    }
}

void FindRequestManager::RemoveFindMatchRectsPendingReply(
    RenderFrameHost* rfh)
{
    auto it = match_rects_.pending_replies.find(rfh);
    if (it == match_rects_.pending_replies.end())
        return;

    match_rects_.pending_replies.erase(it);
    if (match_rects_.pending_replies.empty()) {
        // All replies are in.
        std::vector<gfx::RectF> aggregate_rects;
        if (match_rects_.request_version != match_rects_.known_version) {
            // Request version is stale, so aggregate and report the newer find
            // match rects. The rects should be aggregated in search order.
            for (RenderFrameHost* frame = GetInitialFrame(true /* forward */); frame;
                 frame = Traverse(frame,
                     true /* forward */,
                     true /* matches_only */,
                     false /* wrap */)) {
                auto it = match_rects_.frame_rects.find(frame);
                if (it == match_rects_.frame_rects.end())
                    continue;

                std::vector<gfx::RectF>& frame_rects = it->second.rects;
                aggregate_rects.insert(
                    aggregate_rects.end(), frame_rects.begin(), frame_rects.end());
            }
        }
        contents_->NotifyFindMatchRectsReply(
            match_rects_.known_version, aggregate_rects, match_rects_.active_rect);
    }
}
#endif

} // namespace content
